1. Field of the Invention
This invention relates to software testing. More particularly this invention relates to improvements in the sampling of an input space during generation of test programs for a software implementation that has been modeled as a finite state machine.
2. Description of the Related Art
In the field of hardware testing, it is common to treat the device under test as a finite state machine (FSM). It has been proposed to similarly automate software testing by representing the software program as a finite state machine, in which transitions are represented as directed edges between states. However, the number of tests required to exhaustively exercise a software program is typically much larger than is required for hardware. Furthermore resources for test execution are limited, and their use constitutes a cost. Accordingly, test engineers have attempted to reduce the number of tests selectively, in order that the test generation process be practical in terms of cost and execution time, recognizing that the testing process must still be reliable. Explosion of the number of test programs that are generated by automatic techniques is a drawback of automatic test program generation.
During the past decade, model-based random test program generators have become popular in processor architectural design verification and software testing. Model-based test generation involves the generation of a suite of tests from an abstract model of an application's behavior. The model is derived from a specification of the application. In many model-based testing situations, the behavioral models are described as finite state machines. Such models describe the possible states of the application and the transitions from state to state caused by operations or stimuli. Test suites generated from these behavior models cover different operation invocation patterns according to the testing goals.
Test engineers use finite state machines to model externally observable behavior, and then use various tools to traverse paths of test actions that connect a sequence of states. They then generate test cases for a variety of purposes, for example, acceptance suites, full functional test suites, and regression test suites. Regression test suites involve a rerun of selected portions of a test suite following a revision of an application.
Because a finite state machine that reflects the specification of a useful software program is typically very large, various approaches have been taken to manage the model, using concise and powerful graphical and textual languages. Various traversal algorithms are applied to the finite state machine for test generation. These algorithms are parameterized by the test engineer at runtime.
The generation of an astronomical number of possible test cases is a well-known software testing problem, which has been exacerbated by the speed of automated test generation. Test engineers deal with this by identifying “equivalence classes” for various attributes of test cases. For example, for a function call argument that must fall within the range of 1 to 5, a test engineer may decide to test the minimum value 1, the maximum value 5, and one value that falls between the minimum and the maximum, such as the value 2. With these decisions, the test engineer places the values 2, 3, and 4 in an “equivalence class”. Each value is considered equivalent to the other two, in the sense that if the test fails for any value in the class, then it will fail for all other values of the class. The recognition of equivalence classes stems from the recognition of inherent properties of the software being tested. In theory, there is one “true” set of equivalence classes for a particular program. Once these classes are correctly ascertained, they will remain static throughout the testing period, or until the software application under test is significantly changed.
Conventional approaches to test generation have common problems that the present invention builds upon. In each case, the number of unique paths, or generated test programs is an exponential function of the number of modeled states and transitions. Thus as the scope of the modeled behavior grows, the time to exhaustively generate test cases, and more significantly, the time needed to execute the generated test cases grows exponentially. This growth places a practical limit on the complexity of the program behavior to which automated test generation can be applied. The invention focuses on the model of the software, and therefore reduces the number of tests to a practical level. In so doing, the invention raises the practical limit on the complexity of the software program to which automated test generation may be applied.
For example, a standard approach to the generation of a test suite for a Java™ class, or any other applications programming interface (API), is to model each of the method calls or interface calls as a transition in a finite state machine (FSM). A particular method may have n parameters, each over an input domain. If each of the input domains is binary, there are 2n possible inputs to the method. Even if the input domain is integer or real, common practice requires testing with five or six different values. Common testing abstractions for very large domains include a minimum value, a maximum value, one or two randomly chosen values, and a value outside the domain. Typically, a model of this interface will have 5n possible test inputs. If, in addition there are several methods that interact, the space of interesting test cases is vast.
A common test planning heuristic is “suspicion testing”, in which “suspected” features of the program are evaluated. For example, aspects of the program that are inherently difficult to implement are suspected to have a relatively high probability of containing defects.
In other approaches, constraints have been imposed on paths or transitions, and if not satisfied, the path would not be tested further.
Typical of prior art approaches for generating test programs is U.S. Pat. No. 5,394,347 to Kita et al. which discloses a method of modeling a specification as an extended finite state machine, then performing a depth-first traversal of the resulting state diagram to generate a path file as a basis for a test program.
U.S. Pat. No. 5,623,499 to Ko et al. discloses a technique for generating a test data sequence of minimal length, employing an extended finite state machine. This technique attempts to balance the number of traversals of the directed edges in order to test values in a predetermined test data set. The test data sequence is constructed using an Euler tour.
In U.S. Pat. No. 5,918,037 to Tremblay et al., it is proposed to employ a test generator that automatically produces test programs based on a finite state machine model of the software. Limiting the number of test programs is achieved by controlling loop execution, and by appropriately setting the coverage level for the model, known as “transition cover testing”. This approach seeks to specify during the test program generation process that each transition within the finite state machine model be exercised once. The generator is capable of specifying different coverage levels for selected portions of the program under test, so that critical portions might be exhaustively tested, while other portions receive less comprehensive testing.
Another model-based generator is the GOTCHA-TCBeans Software Test Tool Kit, which has been developed by International Business Machines Corporation, New Orchard Road, Armonk, N.Y. 10504. This tool provides a framework designed to assist testers in developing, executing and organizing function tests directed against Application Program Interfaces (APIs) and software protocols written in Java, C or C++.
Attempts have been made to reduce the number of test cases in general software testing systems using combinatorics. U.S. Pat. No. 5,542,043 proposes generating a minimum number of test cases by defining tables that contain related field values, and then generating a corresponding table of test cases. The algorithms employed for the tables are capable of producing a minimal number of test cases in which elements interact in any given degree.
An approach for minimizing the cost of software testing was put forward in the document The AETG System: An Approach to Testing Based on Combinatorial Design. Cohen, D. M., Dalal, S. R., Fredman, M. L., and Patton, G. C. IEEE Transaction on Software Engineering. Volume 23, Number 27, July 1997. This document discloses using test suites generated from combinatorial designs. This approach involves identifying parameters that define the space of possible test scenarios, than selecting test scenarios in such a way as to cover all the pairwise (or t-wise) interactions between these parameters and their values.
A similar approach was disclosed earlier for hardware testing in the document Iterative Exhaustive Pattern Generation for Logic Testing, D. T. Tang and C. L. Chen, IBM J. Res. Develop 28 (1984), 212-219, and the document Exhaustive Test Pattern Generation with Constant Weight Vectors, D. T. Tang and L. S. Woo. IEEE Trans. Computers 32 (1983) 1145-1150. This approach is familiar to statisticians, and has been used in the design of agricultural experiments since the 1940's. The statistical analysis of such experiments is facilitated if every interaction is covered the same number of times. However, the above-noted Cohen et. al. document points out that in the testing of software it is often sufficient to generate test suites such that each interaction is covered at least once.